package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/26 21:51
 */
public class C33 {


    public static int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

    public static int compare(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target) return i;
        }
        return -1;
    }


    public static void main(String[] args) {
//        int[] arr = {4, 5, 6, 7, 0, 1, 2};
//        int target = 5;
//        System.out.println(search(arr, target));


        int times = 100000;
        int maxLen = 2000;
        for (int i = 0; i < times; i++) {
            int[] arr = generateArr(maxLen);
            int target = (int) (Math.random() * maxLen);
            int ans1 = search(arr, target);
            int ans2 = compare(arr, target);
            if (ans1 != ans2) {
                System.out.println("OOPS");
                System.out.println(Arrays.toString(arr));
                System.out.println("target: " + target);
                System.out.println(ans1);
                System.out.println(ans2);
                break;
            }
        }

    }

    public static int[] generateArr(int maxLen) {
        maxLen = (int) (Math.random() * maxLen) + 1;
        int[] res = new int[maxLen];
        int K = (int) (maxLen * Math.random());
        int v = 0;
        for (int i = K; i < maxLen; i++) {
            res[i] = v++;
        }
        for (int i = 0; i < K; i++) {
            res[i] = v++;
        }
        return res;
    }

}
